package com.itzmn.newcode.offer;

import java.util.ArrayList;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/17 10:36
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description:  剑指Offer 求安从小到大的第n个丑数
 *
 *  什么是丑数，只有2,3，5质因子的数。
 *  思路：如果是丑数，那么就只包含这几个因子
 */
public class IsUglyNumber {

    public static void main(String[] args) {

        System.out.println(new IsUglyNumber().GetUglyNumber_Solution(8));

    }
    public int GetUglyNumber_Solution(int index) {
        if (index < 7){
            return index;
        }
        //维护三个索引,以及当前三个队列最小的值
        int p0=0;int p1=0;int p2=0;int newNum=1;
        ArrayList<Integer> integers = new ArrayList<>();
        integers.add(newNum);

        while (integers.size()<index){

            //得到三个队列中的最小值
            newNum = Math.min(integers.get(p0)*2,Math.min(integers.get(p1)*3,integers.get(p2)*5));

            //说明是第一个队列的值最小
            if (newNum == integers.get(p0)*2){
                p0++;
            }
            if (newNum == integers.get(p1)*3){
                p1++;
            }
            if (newNum == integers.get(p2)*5){
                p2++;
            }

            integers.add(newNum);

        }
        return newNum;
    }



}
